//Given an m x n grid of characters board and a string word, return true if word
// exists in the grid. 
//
// The word can be constructed from letters of sequentially adjacent cells, wher
//e adjacent cells are horizontally or vertically neighboring. The same letter cel
//l may not be used more than once. 
//
// 
// Example 1: 
//
// 
//Input: board = [["A","B","C","E"],
//                ["S","F","C","S"],
//                ["A","D","E","E"]], word =
// "ABCCED"
//Output: true
// 
//
// Example 2: 
//
// 
//Input: board = [["A","B","C","E"],
//                ["S","F","C","S"],
//                ["A","D","E","E"]], word =
// "SEE"
//Output: true
// 
//
// Example 3: 
//
// 
//Input: board = [["A","B","C","E"],
//                ["S","F","C","S"],
//                ["A","D","E","E"]], word =
// "ABCB"
//Output: false
// 
//
// 
// Constraints: 
//
// 
// m == board.length 
// n = board[i].length 
// 1 <= m, n <= 6 
// 1 <= word.length <= 15 
// board and word consists of only lowercase and uppercase English letters. 
// 
//
// 
// Follow up: Could you use search pruning to make your solution faster with a l
//arger board? 
// Related Topics 数组 回溯算法 
// 👍 918 👎 0


package leetcode.editor.cn;

import org.junit.Assert;

//Java：Word Search
class P79WordSearch {
    public static void main(String[] args) {
        Solution solution = new P79WordSearch().new Solution();
        // TO TEST
        Assert.assertEquals(solution.exist(new char[][]{
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}}, "ABCCDE"), true);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        boolean[][] visited;
        boolean exist = false;

        public boolean exist(char[][] board, String word) {
            visited = new boolean[board.length][board[0].length];
            exist(board, 0, 0, word, 0);
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    exist(board, i, j, word, 0);
                    if (exist == true) {
                        break;
                    }
                }
            }
            return exist == true;
        }

        private void exist(char[][] board, int x, int y, String word, int start) {

            if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) {
                return;
            }
            if (board[x][y] == word.charAt(start)) {
                if (start >= word.length() - 1) {
                    exist = true;
                    return;
                }
                int[][] pos = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
                boolean result = false;
                for (int[] po : pos) {
                    int xm = x + po[0], ym = y + po[1];
                    if (xm < 0 || ym < 0 || xm >= board.length || ym >= board[0].length) {
                        continue;
                    }
                    if (visited[xm][ym] == false) {
                        visited[x][y] = true;
                        result = true;
                        exist(board, xm, ym, word, start + 1);
                        visited[x][y] = false;
                    }
                }
                if (result == false) {
                    return;
                }
            }

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}